home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / xdiff 1.0 / xdiff1.0.src / xdiff.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-07-10  |  6.1 KB  |  296 lines  |  [TEXT/MPS ]
  1.  
  2. # define MASTERDEF
  3.  
  4. # include <stdio.h>
  5. # include <fcntl.h>
  6. # include "xdiff.h"
  7.  
  8. static char space[1024];
  9. /*
  10. *  xdiff
  11. *  Compares two text files and outputs a differences file which can be used to
  12. *  execute duplicate edits on another system.
  13. *
  14. *
  15. *  National Center for Supercomputing Applications
  16. *  March 7, 1988
  17. *  Completed June, 1989
  18. *
  19. *  This program is in the public domain
  20. *
  21. *  Tim Krauskopf
  22. */
  23.  
  24. /***********************************************************/
  25. /*  loadfile
  26. *  Load and compute id checksums for a new file.
  27. *  Efficiency counts!
  28. *
  29. *  Loads the file structure with every applicable field.
  30. *
  31. *  Returns 0 if ok, negative on error.
  32. */
  33. loadfile(f)
  34.     diffile *f;
  35.     {
  36.     register char *p;
  37.     register int i;
  38.     register int32 sum,sumt;
  39.      struct lndiff *sp;
  40.     int32 j;
  41.     char *endp;
  42.     
  43.     if (0 > (f->fd = open(f->fn,O_RDONLY))) {
  44.         return(-1);
  45.     }
  46.     
  47.     f->len = lseek(f->fd,(long)0,2);        /* find length of file */
  48.     lseek(f->fd,(long)0,0);                    /* back to beginning */
  49.     
  50.     if (f->store)                            /* if previous allocation, lose it */
  51.         free(f->store);
  52.         
  53.     if (NULL == (f->store = malloc(f->len+10))) {
  54.         return(-2);
  55.     }
  56.     
  57.     if (0 >= (f->len = read(f->fd,f->store,f->len))) {
  58.         return(-3);
  59.     }
  60.     
  61.     close(f->fd);
  62.     
  63. /*
  64. *  len now has the exact number of bytes read, and that is what we'll work with.
  65. *
  66. *  Allocate storage by counting the number of end-of-lines in the file and 
  67. *  then allocate that number of line control blocks.
  68. */
  69.     f->store[f->len] = '\n';        /* need anchoring line end */
  70. #ifdef fix
  71.     f->store[++f->len] = '\n';        /* double anchor for fixup */
  72. #endif
  73.  
  74.     p = f->store;
  75.     endp = f->store + f->len;        /* end of scanning */
  76.     i = 0;                            /* end of lines found */
  77.     while (p < endp)
  78.         if (*p++ == '\n')
  79.             i++;
  80.     
  81.     f->lines = i;
  82.     f->curstart = 0L;
  83.     
  84.     if (f->lstore)                    /* free previous allocation */
  85.         free((Ptr) f->lstore);
  86.         
  87.     if (NULL == (f->lstore = (struct lndiff *)malloc(
  88.         (i+1) * sizeof(struct lndiff)  ))) {
  89.         return(-4);
  90.     }
  91. /*
  92. *  fill line control structure with hashing data.  One in 4 billion chance
  93. *  of two non-matching lines accidentally matching.
  94. */
  95.     p = f->store;
  96.     endp = f->store + f->len;        /* end of scanning */
  97.     sp = f->lstore;
  98.     j = 0;                            /* counting segments */
  99.     sumt = 0L;
  100.     
  101.     while (p < endp) {
  102.         sum = 0L;
  103.         sp->ld = p;                    /* start of this line's data */
  104.         while (*p != '\n') {
  105.             if (sum & 0x8000000L)      /* rotate operation */
  106.                 sum = (sum & 0x7fffffffL) + 1;
  107.             sum = (sum << 1) + (*p++);
  108.         }
  109.         sp->id = sum;
  110.         sumt += sum;
  111.         sp->num = j++;
  112.         sp++; p++;
  113.     }
  114.     
  115.     sp->ld = endp;                    /* anchor the endpoint */
  116.     f->tsum = sumt;
  117. #ifdef UNIX
  118.     printf(" %ld bytes, %ld lines\n",f->len,f->lines);
  119. #endif    
  120.     return(0);
  121.     
  122. }
  123.  
  124. /*************************************************************/
  125. /*  compfiles
  126. *   Compare two loaded file structures and output the commands
  127. *   required to build the second structure starting with only
  128. *   the first file.
  129. *
  130. *   returns 0 if ok, negative for errors
  131. */
  132. compfiles(f1,f2,dp)
  133.     diffile *f1,*f2;
  134.     FILE *dp;
  135.     {
  136.     register int i,j;
  137.     register struct lndiff *lp1,*lp2;
  138.     struct lndiff *end2;
  139.     char *p;
  140.  
  141. /*
  142. *  write some file info
  143. */
  144.     fprintf(dp,"XDIFF update file for: %s\n",f2->fn);
  145. /*
  146. *  write the two file checksums as the first data line
  147. */
  148.     fprintf(dp,"x%ld,%ld\n",f1->tsum,f2->tsum);
  149. /*
  150. *  For each line in the second file, find it in the first file.
  151. *  For each line found, determine largest block and output a command.
  152. */
  153.     lp2 = f2->lstore;            /* start of second file */
  154.     f2->curstart = 0;
  155.     end2 = f2->lstore + f2->lines;
  156.     while (lp2 < end2) {        /* traverse second file */
  157.     
  158.         i = firstsrch(f1,f2);    /* try to find a match */
  159.         if (i < 0) {            /* no match */
  160.             p = lp2->ld;        /* start of line to write out */
  161.             lp2++;                /* next line struct */
  162.             f2->curstart++;
  163.             fputc('a',dp);        /* write signal character */
  164.             fwrite(p,1,(int)(lp2->ld - p),dp);    /* write out line */
  165.         }
  166.         else {                    /* find length of block */
  167.  
  168.             j = i;                /* save starting line # of block */
  169.             lp1 = f1->lstore + i;    /* where block must start */
  170.             do {                      /* expand block */
  171.                 lp2++; lp1++;
  172.                 f2->curstart++;    /* position in file2 */
  173.                 f1->curstart++;
  174.                 i++;            /* how many lines */
  175.             } while (lp2 < end2 && lp2->id == lp1->id); 
  176.             
  177.             fprintf(dp,"c%d,%d\n",j,i-1);
  178.         }
  179.         
  180.         
  181.     }  /* end traverse of second list */
  182.         
  183.     return(0);
  184. }
  185.  
  186. /****************************************************************/
  187. /*  firstsrch()
  188. *  find the first matching id number from the first file
  189. *  Definitely a O(n) search - linear.
  190. */
  191.  
  192. firstsrch(f1,f2)
  193.     diffile *f1,*f2;
  194.     {
  195.     register uint32 i,lno;
  196.     struct lndiff *ln1,*ln2,*endln,*stopln;
  197.     
  198.     ln2 = f2->lstore + f2->curstart; 
  199.     i = ln2->id;
  200.     ln1 = f1->lstore + f1->curstart;    /* start of search */
  201.     lno = f1->curstart;
  202.     endln = f1->lstore + f1->lines;        /* mid point of search */
  203.     stopln = ln1;                        /* end of search is where it started */
  204.     
  205.     while (ln1 < endln) {
  206.         if (ln1->id == i)
  207.             return(lno);
  208.         lno++;
  209.         ln1++;                /* next line to check */
  210.     }
  211.     
  212.     ln1 = f1->lstore;        /* back to beginning */
  213.     lno = 0L;
  214.     
  215.     while (ln1 < stopln) {
  216.         if (ln1->id == i)
  217.             return(lno);
  218.         lno++;
  219.         ln1++;
  220.     }
  221.     
  222.     return(-1);                /* not found */
  223.     
  224.     
  225. }
  226.  
  227.  
  228. #ifdef UNIX
  229.  
  230. diffile f1,f2;
  231.  
  232. FILE *diffp;
  233.  
  234. main(argc,argv)
  235.     int argc;
  236.     char *argv[];
  237.     {
  238.     int32 dlen;
  239.     
  240.     if (argc < 2) {
  241.         puts(" Usage: xdiff filename [diff_filename]");
  242.         puts(" The control file is always prefixed with 'c.'");
  243.         exit(1);
  244.     }
  245.  
  246.     strcpy(f1.fn,"c.");            /* control file prefix */
  247.     strcat(f1.fn,argv[1]);
  248.     strcpy(f2.fn,argv[1]);        /* file to "diff" */
  249.     
  250.     printf("Loading control file: %s\n",f1.fn);
  251.     
  252.     if (loadfile(&f1)) {
  253.         fprintf(stderr," Cannot load file: %s\n",f1.fn);
  254.         exit(1);
  255.     }
  256.     
  257.     printf("Loading edited file: %s\n",f2.fn);
  258.     
  259.     if (loadfile(&f2)) {
  260.         fprintf(stderr," Cannot load file: %s\n",f2.fn);
  261.         exit(1);
  262.     }
  263.     
  264.     if (argc >= 3) {                /* where to send results */
  265.         diffp = fopen(argv[2],"w");
  266.         printf("Writing update information to: %s\n",argv[2]);
  267.     }
  268.     else {
  269.         diffp = stdout;
  270.         puts("Writing update information to: stdout");
  271.     }
  272.     
  273.     if (NULL == diffp) {
  274.         puts(" Cannot open diff output ");
  275.         exit(1);
  276.     }
  277.     
  278.     compfiles(&f1,&f2,diffp);
  279.     
  280.     dlen = ftell(diffp);
  281.     printf("Update file is %ld bytes - done.\n",dlen);
  282.     
  283.     fclose(diffp);
  284.     exit(0);
  285. }
  286.  
  287. putit(x,y,s)
  288.     int x,y,s;
  289.     {
  290.     puts(s);
  291.     
  292. }
  293.  
  294. #endif
  295.  
  296.